package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2316. 统计无向图中无法互相到达点对数
 * <p>
 * 给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，
 * 其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
 * 请你返回 无法互相到达 的不同 点对数目 。
 * <p>
 * User:Mr.Du
 * Date:2024/4/18
 * Time:9:36
 */
public class CountPairs {

    int[] roots;
    int[] size;
    /**
     * 统计无向图中无法互相到达点对数
     *
     * @param n 节点的数量。
     * @param edges 边的数组，每个边由两个节点索引组成。
     * @return 返回满足条件的对数。
     */
    public long countPairs(int n, int[][] edges) {
        // 初始化根节点和各节点的大小
        roots = new int[n];
        size = new int[n];
        for(int i = 0;i < n;i++){
            roots[i] = i;
            size[i] = 1;
        }
        // 根据边数组进行并查集操作
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            this.union(x, y);
        }
        long total = 0, t = 0;
        // 计算结果
        for(int i = 0;i < n;i++){
            if(i == this.roots[i]){
                total += t * this.size[i];
                t += this.size[i];
            }
        }
        return total;
    }

    /**
     * 找根
     *
     * @param x 要查找根节点的元素值。
     * @return 返回元素x的根节点。
     */
    public int findRoots(int x){
        // 如果当前元素是根节点，则返回该元素本身
        if(roots[x] == x){
            return x;
        }
        // 否则，递归查找并更新根节点
        return roots[x] = findRoots(roots[x]);
    }

    /**
     * 将并查集中的两个集合合并。
     * @param x 第一个集合的元素
     * @param y 第二个集合的元素
     * 该方法不返回任何值，它的作用是将元素x和y所在的集合合并为一个集合。
     */
    public void union(int x, int y){
        // 查找x和y的根节点
        int p = findRoots(x), q = findRoots(y);
        // 如果x和y已经在同一个集合中，无需合并，直接返回
        if(p == q) return;
        // 保证p的根节点的size不小于q的根节点的size
        if(size[p] < size[q]){
            int tmp = p;
            p = q;
            q = tmp;
        }
        // 将p所在集合合并到q所在集合
        roots[p] = q;
        // 更新合并后的集合的大小
        size[q] += size[p];
    }



}
